import java.util.Random;

/**
 * 面试题 17.14. 最小K个数
 * https://leetcode.cn/problems/smallest-k-lcci/description/
 */
class Solution {
    public int[] smallestK(int[] arr, int k) {
        qsort(arr, 0, arr.length - 1, k);
        int[] result = new int[k];
        for(int i = 0; i < k; i++) {
            result[i] = arr[i];
        }
        return result;
    }

    public void qsort(int[] arr, int l, int r, int k) {
        if(l >= r) {
            return;
        }
        //数组分三块
        int key = arr[new Random().nextInt(r - l + 1) + l];
        int i = l, left = l - 1, right = r + 1;
        while(i < right) {
            if(arr[i] < key) swap(arr, ++left, i++);
            else if(arr[i] == key) i++;
            else swap(arr, --right, i);
        }
        //分完三块去里面判断，找最小k,分类讨论
        int a = left - l + 1, b = right - left - 1;
        if(a >= k) qsort(arr, l, left, k);
        else if(a + b >= k) return;
        else qsort(arr, right, r, k - a - b);
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}